package com.algrithom.graph.mincreatetree;

/**
 * 最小生成树 存储结构为：邻接矩阵
 *
 * @author think
 * @version 1.0.0
 * @since 2020/3/8
 */
public class PrimAlg {
    
    /**
     * 求图最小生成树的PRIM算法 基本思想：假设N=(V,{E})是联通网，TE是N上的最小生成树中的变得集合。算法从U={u0}(u0属于V)，
     * TE={}开始，重复执行下述操作：在所有的u属于U，v属于V-U的边（u，v）属于E中找到一条代价最小
     * 的边（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE}) 为N的最小生成树。
     *
     * @param graph 图
     * @param start 开始节点
     * @param n 图中节点数
     */
    public static void primAlg(int[][] graph,int start,int n){
        int[][] mins = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i == start) {
                mins[i][0] = -1;
                mins[i][1] = 0;
            } else if (graph[start][i] != -1) {
                mins[i][0] = start;
                mins[i][1] = graph[start][i];
            } else {
                mins[i][0] = -1;
                mins[i][1] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n - 1; i++) {
            int minV = -1;
            int minW = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (mins[j][1] != 0 && minW > mins[j][1]) {
                    minW = mins[j][1];
                    minV = j;
                }
            }
            mins[minV][1] = 0;
            System.out.println("最小生成树的第" + i + "条最小边=<" + mins[minV][0] + "," + minV + ">，权重=" + minW);
            for (int j = 0; j < n; j++) {
                if (mins[j][1] != 0) {
                    if (graph[minV][j] != -1 && graph[minV][j] < mins[j][1]) {
                        mins[j][0] = minV;
                        mins[j][1] = graph[minV][j];
                    }
                }
            }
        }
    }
}
